#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
#include "LongestCommonSubsequence.h"

//strictly increasing
namespace {
//method one, Time=O(nlgn)
//call bsearch(x,m,i,0,m.size()-1 )
int bsearch(const std::vector<int> & x, const std::vector<int> & m, int i, int left, int right ) { //return j such that x[m[j-1]] < x[i] <= x[m[j]]
	while (left <= right) {
		int mid = (left+right)/2;
		if (x[i] == x[m[mid]])
			return mid;
		else if (x[i] < x[m[mid]] )
			right = mid - 1;
		else
			left = mid + 1;
	}
	//now left > right (left = right + 1)
	if ( x[i] < x[m[left]] )
		return left;
	else
		return right;
}
//m.size() is the length of LIS
//m[i] stores the index of the last element of sequence of length i
int lis_scan(const std::vector<int> & x, std::vector<int> &p, std::vector<int> & m) {
	if (x.size() == 0)
		return 0;
	m.resize(0);
	if (x.size() >= 1) {
		p[0] = -1;
		m.push_back(0);
	}
	for (int i = 1; i < x.size(); ++i) {
		if (x[i] > x[m[m.size()-1]]) {
			p[i] = m[m.size()-1];
			m.push_back(i);
		}
		else { // x[i] <= x[m[old_length-1]]
			int j = bsearch(x,m,i,0,m.size()-1);
			m[j] = i;
			if (j == 0 )
				p[i] = -1;
			else
				p[i] = m[j-1];
		}
	}
	return m.size();
}

//use print_lis(x,p,m[m.size()-1])
void print_lis(const std::vector<int> & x, const std::vector<int> &p, int last) {
	std::stack<int> s;
	while (last >= 0) {
		s.push(x[last]);
		last = p[last];
	}
	while (!s.empty() ) {
		std::cout << s.top() << ' ';
		s.pop();
	}
	std::cout << std::endl;
}

void print_lis_recursive(const std::vector<int> & x, const std::vector<int> &p, int last) {
	if (last == -1)
		return;
	print_lis_recursive(x,p,p[last]);
	std::cout << x[last] << ' ';
}

//method two, call the subroutine of longest Common Subsequence, Time = O(n^2)
void lis_using_lcs(int * x, int n) {
	std::vector<int> y(x, x+n);
	std::sort(y.begin(),y.end());
	for(int i = 0; i< n; ++i) {
		x[i] += '0';
		y[i] += '0';
	}
	test_lcs_internal(x,n,y.data(),n);
}

//method three, dynamic programming built from scratch
//for a sequence from s_1 to s_n, l_i represents the longest increasing subsequence ending at s_i, l_0 = 0
//l_i = max(l_j) + 1, for 0 < j < i and s_j < s_i
//the optimal length is max(l_i) 1 < i <= n
//let p[i] stores the predecessor index of sequence ending with s_i, if no predecessor, p[i] = -1;
//return the longest strictly increasing subsequence
int lis_dp(const std::vector<int> & s, std::vector<int> & l, std::vector<int> & p) {
	const int n = s.size();
	l.resize(n+1);
	p.resize(n+1,-1);
	l[0] = 0;
	for ( int i = 1; i <= n; ++i) {
		l[i] = 1;
		p[i] = -1;
		for ( int j = 1; j < i; ++j) {
			if (s[j-1] < s[i-1] && l[j] + 1 > l[i]){
				l[i] = l[j] + 1;
				p[i] = j;
			}
		}
	}
	//print
	auto si = std::max_element(l.begin(),l.end());
	int i = si - l.begin();
	if (i == 0)
		return 0;
	std::stack<int> stack;
	while(i != -1) {
		stack.push(s[i-1]);
		i = p[i];
	}
	while(!stack.empty()){
		int k = stack.top();
		stack.pop();
		std::cout << k << " ";
	}
	std::cout << std::endl;
	return *si;
}
}
void test_lis() {
	int xa[] = {3,4,5,1,2};
	std::vector<int> x(xa, xa+sizeof(xa)/sizeof(int));
	std::vector<int> p(x.size(),-1);
	std::vector<int> m;
	std::cout << "The length of longest increasing subsequence is " <<  lis_scan(x,p,m) << std::endl;
	print_lis(x,p,m[m.size()-1]);
	print_lis_recursive(x,p,m[m.size()-1]); std::cout << std::endl;
	lis_using_lcs(xa,5);
	std::vector<int> l, p1;
	lis_dp(x,l,p1);

	
	std::cout << " ***************************** \n";
	int xb[] = {3,4,5,1,2,3,6};
	x.resize(sizeof(xb)/sizeof(int));
	for ( int i = 0; i < x.size(); ++ i)
		x[i] = xb[i];
	p.resize(x.size(),-1);
	m.resize(0);
	std::cout << "The length of longest increasing subsequence is " <<  lis_scan(x,p,m) << std::endl;
	print_lis(x,p,m[m.size()-1]);
	print_lis_recursive(x,p,m[m.size()-1]); std::cout << std::endl;
	lis_using_lcs(xb,7);
	lis_dp(x,l,p1);
}